#include "quicksort.h"
#include <QScopeGuard>

QuickSort::QuickSort(QObject *parent)
    : SortBase{parent}
{
    animation.setStartValue(0.0);
    animation.setEndValue(1.0);
    animation.setEasingCurve(QEasingCurve::OutQuart);
    animation.setLoopCount(1);
    connect(&animation, &QVariantAnimation::finished, &loop, &QEventLoop::quit);
    connect(&animation, &QVariantAnimation::valueChanged, this, &SortBase::updateRequest);
}

void QuickSort::sort(size_t num_of_elem, int interval)
{
    // ensure calling setRunState(false) and update at the end of function
    auto guard = qScopeGuard([this] {
        setRunState(false);
        emit updateRequest();
    });

    stop();
    if (arr.size() != num_of_elem)
        randomArray(num_of_elem);
    setRunState(true);

    this->interval = interval;
    QSort(0, (int) num_of_elem - 1);
}

void QuickSort::stop()
{
    setRunState(false);
    animation.stop();
    loop.quit();
    emit updateRequest();
}

void QuickSort::draw(QPainter *painter, int width, int height)
{
    painter->setPen(QColor(200, 200, 200));
    const size_t len = arr.size();
    const size_t max_elem = *(std::max_element(arr.begin(), arr.end()));

    // border
    constexpr int left_space = 0;
    constexpr int right_space = 0;
    constexpr int top_space = 30;
    constexpr int bottom_space = 50;

    // space width between two column
    constexpr int item_space = 10;

    const int text_height = painter->fontMetrics().height();

    // distance between column and number text
    constexpr int text_space = 15;

    // item width is dynamically adjusted according to the window width
    const double item_width = (width + item_space - left_space - right_space) / (double) len
                              - item_space;
    const double item_bottom = height - bottom_space;

    // item height is also dynamically adjusted according to the window height
    const double height_factor = (height - top_space - bottom_space) / (double) max_elem;

    // current drawing column width and height
    double item_left = 0;
    double item_height = 0;

    // we will elevate the pivot
    double bottom_offset = 0;

    QColor color;
    QString text;
    for (int i = 0; i < (int) len; i++) {
        // position of the column
        item_left = left_space + i * (item_width + item_space);
        item_height = height_factor * arr.at(i);
        bottom_offset = 0;

        // default color and text of the column
        color = QColor(200, 200, 200);
        text = QString::number(arr.at(i));

        // current comparing column
        if (runState()) {
            // if column is at sorting area
            if (i >= sortLow && i <= sortHigh) {
                color = QColor(0, 170, 255);
                if (i >= currHigh || i <= currLow) {
                    if (arr.at(i) < pivot_value) {
                        color = QColor(0, 220, 0);
                    } else {
                        color = QColor(230, 0, 0);
                    }
                }
            }

            // if column is the pivot
            if (i == pivot_index) {
                color = QColor(255, 170, 0);
                text = QString("[%1]").arg(QString::number(pivot_value));
                item_height = height_factor * pivot_value;
                bottom_offset = 10;
            }

            // if column is the current swapping one
            if (swapFlag && (i == swapFrom || i == swapTo)) {
                int offset = animation.currentValue().toDouble() * int(swapFrom - swapTo)
                             * (item_width + item_space);

                item_left += (i == swapFrom) ? (-offset) : offset;
            }
        }

        // draw text
        painter->drawText(item_left, item_bottom + text_height + text_space, text);

        // draw rect
        painter->fillRect(item_left,
                          item_bottom - item_height - bottom_offset,
                          item_width,
                          item_height,
                          color);
    }

    painter->fillRect(10, 12, 10, 10, QColor(0, 170, 255));
    painter->drawText(30, 20, "Sorting Area");
    painter->fillRect(10, 32, 10, 10, QColor(255, 170, 0));
    painter->drawText(30, 40, "Pivot");
    painter->fillRect(10, 52, 10, 10, QColor(0, 220, 0));
    painter->drawText(30, 60, "< Pivot value");
    painter->fillRect(10, 72, 10, 10, QColor(230, 0, 0));
    painter->drawText(30, 80, "> Pivot value");
}

void QuickSort::QSort(int low, int high)
{
    if (low >= high)
        return;

    sortLow = currLow = low;
    sortHigh = currHigh = high;

    // partition
    pivot_index = low;
    pivot_value = arr[low];

    int &i = currLow, &j = currHigh;
    while (i < j) {
        // Move small number to the left side of pivot
        while (i < j && arr[j] >= pivot_value) {
            wait(interval);
            j--;
            if (!runState())
                return;
            emit updateRequest();
        }

        /*
            1. It's safe to call QSwap on every iteration.
            2. However, when condition (i<j) is not met, calling it only wait 3 interval
            and doesn't do any "swap" at all. From the user's view, they may think it gets stuck.
            3. That's why we add an if check, to only call QSwap when (i<j)
        */
        if (i < j)
            // arr[i] = arr[j]
            QSwap(j, i);

        // Move big number to the right side of pivot
        while (i < j && arr[i] <= pivot_value) {
            wait(interval);
            i++;
            if (!runState())
                return;
            emit updateRequest();
        }

        if (i < j)
            // arr[j] = arr[i]
            QSwap(i, j);
    }
    arr[i] = pivot_value;
    wait(interval);

    // recursion
    if (!runState())
        return;

    QSort(low, i - 1);

    if (!runState())
        return;

    QSort(i + 1, high);
}

void QuickSort::QSwap(int from, int to)
{
    swapFlag = true;
    swapFrom = from;
    swapTo = to;

    wait(interval * 3);

    if (runState()) {
        pivot_index = from;
        arr[to] = arr[from];
        swapFlag = false;
    }
}

void QuickSort::wait(int ms)
{
    // we use Eventloop to delay animation
    animation.setDuration(ms);
    animation.start();
    loop.exec();
}

void QuickSort::skip()
{
    this->interval = 1;
}
